home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / node_partition.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.4 KB  |  53 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.10 Node partitions (node\_partition)}
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance of the data type $node\_partition$ is a partition of the nodes
  8. of a graph $G$.
  9.  
  10.  
  11. \def\name{$node\_partition$}
  12. \def\type{node\_partition}
  13.  
  14. \bigskip
  15. {\bf 2. Creation}
  16.  
  17.  
  18. \create P (G)
  19.  
  20. creates a \name\ \var\ containing for every node $v$ in $G$ a block $\{v\}$. 
  21.  
  22.  
  23.  
  24. \bigskip
  25. {\bf 3. \operations}
  26.  
  27. \+\cleartabs & \hskip 1.5truecm & \hskip 6.5truecm &\cr
  28. \+\op bool  same\_block   {node\ v,\ node\ w}  
  29.                              {returns true if $v$ and $w$ belong to the }
  30. \+\nop                       {same block of \var.}
  31. \smallskip
  32. \+\op void union\_blocks {node\ v,\ node\ w} 
  33.                              {unites the blocks of \var\ containing nodes}
  34. \+\nop                       {$v$ and $w$.}
  35. \smallskip
  36. \+\op node find {node\ v}    {returns a canonical representative node of}
  37. \+\nop                       {the block that contains node $v$.}
  38. \smallskip
  39.  
  40.  
  41. \bigskip
  42. {\bf 4. Implementation}
  43.  
  44. A node partition for a graph $G$ is implemented by a combination of a 
  45. partition $P$ and a node array of $partition\_item$ associating with 
  46. each node in $G$ a partition item in $P$. Initialization takes linear time,
  47. union\_blocks takes time $O(1)$ (worst-case), and same\_block and find take 
  48. time $O(\alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
  49. is the number of nodes of $G$.
  50.  
  51. \vfill\eject
  52.  
  53.